package thired.class21_AC;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Class02_AC2 {
    public static class Node{
        public String end;
        public Node[] nexts;
        public Node fail;
        public  boolean isEnd;

        public Node(){
            end = null;
            nexts = new Node[26];
            fail = null;
            isEnd = false;
        }
    }

    public static class ACAutomation{
        private Node root;

        public ACAutomation() {
            root = new Node();
        }

        public void insert(String s){
            char[] str = s.toCharArray();
            Node cur = root;
            int index = 0;
            for (char c : str) {
                 index = c - 'a';
                if(cur.nexts[index] == null){
                    cur.nexts[index] = new Node();
                }
                cur =  cur.nexts[index];
            }
            cur.end = s;
        }
        public void build(){
            Node cur = null;
            Queue<Node> queue = new LinkedList<>();
            queue.add(root);
            Node cfail = null;
            while(!queue.isEmpty()){
                cur = queue.poll();
                for (int i = 0; i < 26; i++) {
                    if (cur.nexts[i] != null) {
                        cur.nexts[i].fail = root;
                        cfail = cur.fail;
                        while (cfail != null){
                            if(cfail.nexts[i] != null){
                                cur.nexts[i].fail = cfail.nexts[i];
                                break;
                            }
                            cfail = cfail.fail;
                        }
                        queue.add(cur.nexts[i]);
                    }

                }
            }
        }


        // 大文章：content
//        public List<String> containWords(String content) {
//            char[] str = content.toCharArray();
//            Node cur = root;
//            Node follow = null;
//            int index = 0;
//            List<String> ans = new ArrayList<>();
//            for (int i = 0; i < str.length; i++) {
//                index = str[i] - 'a'; // 路
//                // 如果当前字符在这条路上没配出来，就随着fail方向走向下条路径
//                while (cur.nexts[index] == null && cur != root) {
//                    cur = cur.fail;
//                }
//                // 1) 现在来到的路径，是可以继续匹配的
//                // 2) 现在来到的节点，就是前缀树的根节点
//                cur = cur.nexts[index] != null ? cur.nexts[index] : root;
//                follow = cur;
//                while (follow != root) {
//                    if (follow.endUse) {
//                        break;
//                    }
//                    // 不同的需求，在这一段之间修改
//                    if (follow.end != null) {
//                        ans.add(follow.end);
//                        follow.endUse = true;
//                    }
//                    // 不同的需求，在这一段之间修改
//                    follow = follow.fail;
//                }
//            }
//            return ans;
//        }
//
//    }
        public List<String> containWords(String content){
            char[] s = content.toCharArray();
            List<String> ans = new ArrayList<>();
            int index = 0;
            Node cur = root;
            Node follow = null;
            for (int i = 0; i < s.length; i++) {
                index = s[i] - 'a';
                while (cur.nexts[index] == null && cur != root) {
                    cur = cur.fail;
                }
                cur = cur.nexts[index] != null ? cur.nexts[index] : root;
                follow = cur;
                while (follow != root){
                if(follow.isEnd){
                    break;
                }
                if(follow.end != null){
                    ans.add(follow.end);
                    follow.isEnd = true;
                }
                follow = follow.fail;
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        ACAutomation ac = new ACAutomation();
        ac.insert("dhe");
        ac.insert("he");
        ac.insert("abcdheks");
        ac.insert("bbbbbb");
        ac.insert("jfafh");
        // 设置fail指针
        ac.build();

        List<String> contains = ac.containWords("abcdhekskdjfafhasldkflskdjhwqaeruv");
        for (String word : contains) {
            System.out.println(word);
        }
    }
}
